|
A biclique attack is a variant of the meet-in-the-middle (MITM) method of cryptanalysis. It utilizes a biclique structure to extend the number of possibly attacked rounds by the MITM attack. Since biclique cryptanalysis is based on MITM attacks, it is applicable to both block ciphers and (iterated) hash-functions. Biclique attacks are known for having broken both full AES and full IDEA, though only with slight advantage over brute force. It has also been applied to the KASUMI cipher and preimage resistance of the Skein-512 and SHA-2 hash functions.〔(Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family )〕 The biclique attack is the best publicly known single-key attack on AES. The computational complexity of the attack is , and for AES128, AES192 and AES256, respectively. It is the only publicly known single-key attack on AES that attacks the full number of rounds.〔 Previous attacks have attacked round reduced variants (typically variants reduced to 7 or 8 rounds). As the computational complexity of the attack is , it is a theoretical attack, which means the security of AES has not been broken, and the use of AES remains relatively secure. The biclique attack is nevertheless an interesting attack, which suggests a new approach to performing cryptanalysis on block ciphers. The attack has also rendered more information about AES, as it has brought into question the safety-margin in the number of rounds used therein. == History == The original MITM attack was first suggested by Diffie and Hellman in 1977, when they discussed the cryptanalytic properties of DES. They argued that the key-size was too small, and that reapplying DES multiple times with different keys, could be a solution to the key-size; however, they advised against using double-DES and suggested triple-DES as a minimum, due to MITM attacks (MITM attacks can easily be applied to double-DES to reduce the security from to just , since one can independently bruteforce the first and the second DES-encryption if they have the plain- and ciphertext). Since Diffie and Hellman suggested MITM attacks, many variations have emerged that are useful in situations, where the basic MITM attack is inapplicable. The biclique attack variant, was first suggested by Khovratovich, Rechberger and Savelieva for use with hash-function cryptanalysis. However, it was Bogdanov, Khovratovich and Rechberger who showed how to apply the concept of bicliques to the secret-key setting including block-cipher cryptanalysis, when they published their attack on AES. Prior to this, MITM attacks on AES and many other block ciphers had received little attention. Mostly due to the need for independent key bits between the two 'MITM subciphers' in order to facilitate the MITM attack — something that is hard to achieve with many modern key schedules, such as that of AES. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Biclique attack」の詳細全文を読む スポンサード リンク
|